# -*- coding: utf-8 -*-            
# @Time : 2023/8/6 16:09
# @Author  : lining
# @FileName: 树的序列化与反序列化.py
"""
https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/
遍历二叉树，返回一个字符串，给当一个字符串，返回一个二叉树
问题：遍历一遍先序，1，2，3，3，3，用先序中序还原，有重复元素不能确定唯一一棵树
（1）会有重复元素，显示的记录，没有子树的记为空
1，2，null，null，3，3，3
这个做先序遍历
                1
          2          3
      4      5    6     7
先序1，2，4，5，3，6，7
"""


class Node():
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

tree = []
def serialization(nodex):
    """
    序列化->树->字符串，传入一个节点，先序遍历
    :param node:
    :return:
    """
    if nodex is None:
        tree.append('None')
        return
    tree.append(str(nodex.value))
    serialization(nodex.left)
    serialization(nodex.right)
    return '|'.join(tree)


def disserialization(s):
    """
    反序列化->字符串->树，传入一个字符串,返回根节点
    :param s:
    :return:
    """
    if not s:
        return
    x = s.split('|')
    root = Node(x[0])
    # 是否左子树
    isleft = True
    current = root
    del x[0]
    # 存放中间的节点
    result = [root]
    while x:
        # 为空直接下一个节点
        if x[0]=='None':
            # 当前是左子树，就到右子树
            if isleft:
                isleft = False
            # 当前是右子树，就返回上一个几点,在增加左子节点的时候放入了当前节点，返回右子树要到当前节点的上一个节点
            else:
                current = result.pop()
                if result:
                    current = result.pop()
            del x[0]
            continue
        node = Node(x[0])
        # 左子树
        if isleft:
            current.left = node
        else:
            current.right = node
            isleft = True
        current = node
        result.append(node)
        del x[0]
    return root

class DeSerialization():
    def __init__(self, s):
        self.stri = s.split('|')
        self.sub = 0


    def deserialization(self):
        if self.stri[self.sub] == 'None':
            self.sub = self.sub + 1
            return
        # 当前节点
        current = Node(int(self.stri[self.sub]))
        self.sub = self.sub+1
        current.left = self.deserialization()
        current.right = self.deserialization()
        return current


a = DeSerialization('1|2|4|8|None|None|None|5|None|None|3|6|None|None|7|None|None').deserialization()
print(a)
# node8 = Node(8)
# node7 = Node(7)
# node6 = Node(6)
# node5 = Node(5)
# node4 = Node(4, node8)
# node3 = Node(3, node6, node7)
# node2 = Node(2, node4, node5)
# node1 = Node(1, node2, node3)
# x = serialization(node1)
# print(x)

